#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode{
	ElemType data;
	struct LNode *next;
} LinkList;

void InitList(LinkList *&L){
	L=(LinkList*)malloc(sizeof(LinkList));
	L->next=NULL;
}

void DestroyList(LinkList *&L){
	LinkList *pre = L, *p=L->next;
	while(p!=NULL){
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}

int ListLength(LinkList *L){
	int n=0;
	LinkList *p = L;
	while(p->next!=NULL){
		n++;
		p=p->next;
	}
	return(n);
}

bool GetElem(LinkList *L,int i,ElemType &e){
	int j = 0;
	LinkList *p = L;
	if (i<=0) return false;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if (p==NULL)
	return false;
	else {
		e = p->data;
		return true;
	}
}

int LocateElem(LinkList *L,ElemType e){
	int i = 1;
	LinkList *p = L->next;
	while(p!=NULL && p->data!=e){
		p= p->next;
		i++;
	}
	if (p==NULL){
		return(0);
	}else{
		return(1);
	}
}

bool ListInsert(LinkList *&L,int i,ElemType e){
	int j = 0;
	LinkList *p = L,*s;
	if (i<=0) return false;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if (p==NULL){
		return false;
	}else{
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
}

bool ListDelete(LinkList *&L,int i,ElemType e){
	int j = 0;
	LinkList *p = L,*q;
	if (i<=0) return false;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if (p==NULL){
		return false;
	}else{
		q=p->next;
		if (q==NULL)
			return false;
		e=q->data;
		p->next=q->next;
		free(q);
		return true;
	}
}

void DispList(LinkList *L){
	LinkList *p=L->next;
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void CreateListF(LinkList *&L,ElemType a[],int n){
	LinkList *s;
	L=(LinkList *)malloc(sizeof(LinkList));
	L->next=NULL;
	for (int i = 0;i<n;i++){
		s=(LinkList*)malloc(sizeof(LinkList));
		s->data=a[i];
		s->next = L->next;
		L->next=s;
	}
}

void CreateListR(LinkList *&L,ElemType a[],int n){
	LinkList *s,*r;
	L=(LinkList*)malloc(sizeof(LinkList));
	r=L;
	for(int i=0;i<n;i++){
		s=(LinkList*)malloc(sizeof(LinkList));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}
